// 滑动窗口 - 经典找最长/短 字串/子数组 问题，都可以使用滑动窗口
// 利用 单调性， 使用 同向双指针 的方法进行优化，使得时间复杂度降低 O(N)
// 定义 双指针 用于维护 窗口 的左右边界
// 进窗口 -> 判断是否出窗口，过程中统计结果

// 例题 8：
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//
//        注意：
//        对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
//        如果 s 中存在这样的子串，我们保证它是唯一的答案。
//
//        示例 1：
//
//        输入：s = "ADOBECODEBANC", t = "ABC"
//        输出："BANC"
//        解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
//        示例 2：
//
//        输入：s = "a", t = "a"
//        输出："a"
//        解释：整个字符串 s 是最小覆盖子串。
//        示例 3:
//
//        输入: s = "a", t = "aa"
//        输出: ""
//        解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//        因此没有符合条件的子字符串，返回空字符串。

// 解题思路：
// 可以使用哈希表维护字符和数量，以及再定义一个变量 count 维护有效字符的个数
// 与例题 6 相同
// 进窗口：统计字符及数量 判断是否为有效字符
// 如果有效字符数量大于等于 t 中字符数量，统计结果，出窗口

public class MinWindow {
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        if(m < n) return "";
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        int[] hash1 = new int['z' - 'A' + 1];
        for(char ch : tArr) hash1[ch - 'A']++;
        int[] hash2 = new int['z' - 'A' + 1];
        int left = 0;
        int right = 0;
        int count = 0;
        int pos = 0;
        int len = Integer.MAX_VALUE;
        while(right < m){
            hash2[sArr[right] - 'A']++;
            if(hash2[sArr[right] - 'A'] <= hash1[sArr[right] - 'A']) count++;
            while(count >= n){
                if(len > right - left + 1) {
                    len = right - left + 1;
                    pos = left;
                }
                hash2[sArr[left] - 'A']--;
                if(hash2[sArr[left] - 'A'] < hash1[sArr[left] - 'A']) count--;
                left++;
            }
            right++;
        }
        if(len == Integer.MAX_VALUE) return "";
        return s.substring(pos, pos + len);
    }
}
